#include <stdio.h>
#include <stdlib.h>
#include "graph.h"

int Init(Graph *graph)
{
     graph->MaxVertex = Default_Vertex_Size;
     graph->NumVertex = graph->NumEdge = 0;
     graph->VertexList = malloc(sizeof(datatype) * graph->MaxVertex);
     //graph->VertexList = calloc(Default_Vertex_Size, sizeof(datatype));
     if (graph->VertexList == NULL)
          return -1;
     graph->Edge = malloc(sizeof(int *) * graph->MaxVertex);
     if (graph->VertexList == NULL)
          return -2;
     for (int i = 0; i < graph->MaxVertex; i++)
     {
          graph->Edge[i] = malloc(sizeof(int) * graph->MaxVertex);
          if (graph->Edge[i] == NULL)
               return -3;
     }
     for (int i = 0; i < graph->MaxVertex; i++)
     {
          for (int j = 0; j < graph->MaxVertex; j++)
          {
               if (i == j)
                    graph->Edge[i][j] = 0;
               else
                    graph->Edge[i][j] = MAX_COST;
          }
     }
     return 0;
}

void Show(Graph *graph)
{
     printf("  ");
     for (int i = 0; i < graph->NumVertex; i++)
          printf("%c ", graph->VertexList[i]);
     printf("\n");
     for (int i = 0; i < graph->NumVertex; i++)
     {
          printf("%c ", graph->VertexList[i]);
          for (int j = 0; j < graph->NumVertex; j++)
          {
               if (graph->Edge[i][j] == MAX_COST)
                    printf("%c ", '@'); //约定'@'在输出时表示无穷大
               else
                    printf("%d ", graph->Edge[i][j]);
          }
          printf("\n");
     }
     printf("\n");
}

int InsertVertex(Graph *graph, datatype vertex)
{
     if (graph->NumVertex == graph->MaxVertex)
          return -1;
     graph->VertexList[graph->NumVertex++] = vertex;
     return 0;
}

int GetVertexPosition(Graph *graph, datatype vertex)
{
     for (int i = 0; i < graph->NumVertex; i++)
     {
          if (graph->VertexList[i] == vertex)
               return i;
     }
     return -1;
}

int InsertEdge(Graph *graph, datatype vertex1, datatype vertex2, type_weight cost)
{
     int p1 = GetVertexPosition(graph, vertex1);
     int p2 = GetVertexPosition(graph, vertex2);
     if (p1 == -1 || p2 == -1)
          return -1;
     if (p1 == p2)
          return -2;
     graph->Edge[p1][p2] = graph->Edge[p2][p1] = cost;
     ++graph->NumEdge;
     return 0;
}

int RemoveVertex1(Graph *graph, datatype vertex)
{
     int pos = GetVertexPosition(graph, vertex);
     if (pos == -1)
          return -1;
     //顶点列表中的删除顶点后的顶点前移
     for (int i = pos; i < graph->NumVertex - 1; ++i)
          graph->VertexList[i] = graph->VertexList[i + 1];
     //统计删除顶点连接的边数
     int numedge = 0;
     for (int i = 0; i < graph->NumVertex; ++i)
     {
          if (graph->Edge[pos][i])
               numedge++;
     }
     //numedge += graph->Edge[pos][i];
     //行上移
     for (int i = pos; i < graph->NumVertex - 1; ++i)
          for (int j = 0; j < graph->NumVertex; ++j)
               graph->Edge[i][j] = graph->Edge[i + 1][j];
     //列上移
     for (int i = pos; i < graph->NumVertex; ++i)
          for (int j = 0; j < graph->NumVertex; ++j)
               graph->Edge[j][i] = graph->Edge[j][i + 1];
     --graph->NumVertex;
     graph->NumEdge -= numedge;
     return 0;
}

int RemoveVertex2(Graph *graph, datatype vertex)
{
     int pos = GetVertexPosition(graph, vertex);
     if (pos == -1)
          return -1;
     int numedge = 0;
     for (int i = 0; i < graph->NumVertex; ++i)
          numedge += graph->Edge[pos][i];
     //修改顶点列表
     graph->VertexList[pos] = graph->VertexList[graph->NumVertex - 1];
     //行覆盖
     for (int i = 0; i < graph->NumVertex; i++)
          graph->Edge[pos][i] = graph->Edge[graph->NumVertex - 1][i];
     //列覆盖
     for (int i = 0; i < graph->NumVertex; i++)
          graph->Edge[i][pos] = graph->Edge[i][graph->NumVertex - 1];
     --graph->NumVertex;
     graph->NumEdge -= numedge;
     return 0;
}

int RemoveEdge(Graph *graph, datatype vertex1, datatype vertex2)
{
     int p1 = GetVertexPosition(graph, vertex1);
     int p2 = GetVertexPosition(graph, vertex2);
     if (p1 == -1 || p2 == -1)
          return -1;
     if (graph->Edge[p1][p2] == 0) //本来就没有边
          return -2;
     graph->Edge[p1][p2] = graph->Edge[p2][p1] = 0;
     --graph->NumEdge;
     return 0;
}

int GetFirstNeighbor(Graph *graph, datatype vertex)
{
     int pos = GetVertexPosition(graph, vertex);
     if (pos == -1)
          return -1;
     for (int i = 0; i < graph->NumVertex; ++i)
     {
          if (graph->Edge[pos][i] == 1)
               return i;
     }
     return -2;
}

int GetNextNeighbor(Graph *graph, datatype vertex1, datatype vertex2)
{
     int p1 = GetVertexPosition(graph, vertex1);
     int p2 = GetVertexPosition(graph, vertex2);
     if (p1 == -1 || p2 == -1)
          return -1;
     for (int i = p2 + 1; i < graph->NumVertex; i++)
     {
          if (graph->Edge[p1][i] == 1)
               return i; //正确返回结果
     }
     return -1;
}

void DestoryGraph(Graph *graph)
{
     free(graph->VertexList);
     graph->VertexList = NULL;
     for (int i = 0; i < graph->MaxVertex; i++)
          free(graph->Edge[i]);
     free(graph->Edge);
     graph->Edge = NULL;
     graph->MaxVertex = graph->NumVertex = graph->NumEdge = 0;
}

int Prim(Graph *graph, datatype vertex)
{
     int n = graph->NumVertex;

     //构造辅助数组
     type_weight *lowcost = malloc(sizeof(type_weight) * n);
     int *mst = malloc(sizeof(int) * n);
     if (lowcost == NULL || mst == NULL)
          return -1;

     //获取起始点的数组下标
     int p = GetVertexPosition(graph, vertex);
     if (p == -1)
          return -2;

     //初始化起始点到其他结点的lowcost,每个结点的起始结点
     for (int i = 0; i < n; i++)
     {
          if (i != p)
          {
               lowcost[i] = graph->Edge[i][p];
               mst[i] = p; 
          }
          else
               lowcost[i] = 0;   //自己到自己的代价为0
     }

     int min, min_index; //lowcost的最小值，最小值的顶点下标
     int begin, end;
     for (int i = 0; i < n - 1; i++)
     {
          //从lowcost数组找寻找最小值
          min = MAX_COST;
          min_index = -1;
          for (int j = 0; j < n; j++)
          {
               if (lowcost[j] != 0 && lowcost[j] < min) //不为0表示没有加入顶点集合
               {
                    min = lowcost[j];
                    min_index = j;
               }
          }

          //打印最低花费的结点连接情况
          begin = mst[min_index];
          end = min_index;
          printf("%c-->%c : %d\n", graph->VertexList[begin], graph->VertexList[end], graph->Edge[begin][end]);

          //将新结点加入
          lowcost[min_index] = 0;

          //更新lowcost
          for (int i = 0; i < n; i++)
          {
               int cost = graph->Edge[i][min_index];
               if (cost < lowcost[i])
               {
                    lowcost[i] = cost;
                    mst[i] = min_index;
               }
          }
     }

     free(lowcost);
     free(mst);

     return 0;
}

//按照草稿本上的Prim算法实现顺序写的
/*
     int *lowcost = malloc(sizeof(int) * graph->NumVertex);
     int *mst = malloc(sizeof(int) * graph->NumVertex);
     if (lowcost == NULL || mst == NULL)
          return -1;
     int p = GetVertexPosition(graph, vertex);
     if (p == -1)
          return -2;
     for (int i = 0; i < graph->NumVertex; i++)
     {
          if (i != p)
               lowcost[i] = graph->Edge[i][p];
          else
               lowcost[i] = 0;
          mst[i] = p;
     }
     for (int i = 0; i < graph->NumVertex - 1; i++)
     {
          int min = MAX_COST,min_index = -1;
          for (int j = 0; j < graph->NumVertex; j++)
          {
               if (lowcost[j] != 0 && lowcost[j] < min)
               {
                    min = lowcost[j];
                    min_index = j;
               }
          }
          int begin = mst[min_index];
          int end = min_index;
          printf("%c-->%c : %d\n",graph->VertexList[begin],graph->VertexList[end],graph->Edge[begin][end]);
          lowcost[min_index] = 0;
          for (int i = 0; i < graph->NumVertex; i++)
          {
               int cost = graph->Edge[i][min_index];
               if (cost < lowcost[i])
               {
                    lowcost[i] = cost;
                    mst[i] = min_index;
               }
          }
     }
     return 0;
*/